home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 July: Mac OS SDK / Dev.CD Jul 96 SDK / Dev.CD Jul 96 SDK1.toast / Development Kits (Disc 1) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc Source Code / Imaging / PolygonClipper / PGPoly.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-22  |  7.3 KB  |  382 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        PGPoly.cpp
  3.  
  4.     Contains:    Polygon structs for the clipper.
  5.  
  6.     Owned by:    Jens Alfke (based on algorithm by A. C. Kilgour)
  7.  
  8.     Copyright:    © 1994 - 1995 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     Change History (most recent first):
  11.  
  12.          <4>     5/25/95    jpa        Only define ff if not already defined.
  13.                                     [1241078, 1253324]
  14.          <3>     12/5/94    jpa        Support right handed coords, e.g. OS/2.
  15.                                     [1203950]
  16.          <2>     9/29/94    RA        1189812: Mods for 68K build.
  17.          <1>     6/15/94    jpa        first checked in
  18.          ---------------------------Moved to ODSOM project.
  19.          <1>      5/9/94    jpa        first checked in
  20.     To Do:
  21.         Exception handling!!
  22.     In Progress:
  23.         
  24. */
  25.  
  26.  
  27. #pragma segment ODPolygonClip
  28.  
  29.  
  30. #ifndef _ALTPOINT_
  31. #include "AltPoint.h"
  32. #endif
  33.  
  34. #ifndef _ALTPOLY_
  35. #include "AltPoly.h"
  36. #endif
  37.  
  38. #ifndef _PGPOLY_
  39. #include "PGPoly.h"
  40. #endif
  41.  
  42. #ifndef _PGEDGE_
  43. #include "PGEdge.h"
  44. #endif
  45.  
  46. #ifndef _PGEVENT_
  47. #include "PGEvent.h"
  48. #endif
  49.  
  50. #ifndef _EXCEPT_
  51. #include "Except.h"
  52. #endif
  53.  
  54. #ifndef _ODDEBUG_
  55. #include "ODDebug.h"
  56. #endif
  57.  
  58.  
  59. // Does the graphics system use right handed (origin at bottom left) coordinates?
  60. #ifdef _PLATFORM_OS2_
  61.     #define RIGHT_HANDED_COORDS 1
  62. #else
  63.     #define RIGHT_HANDED_COORDS 0
  64. #endif
  65.  
  66.  
  67. #ifndef ff
  68. #define ff(INT)        ( (ODFixed)(INT) <<16 )
  69. #endif
  70.  
  71.  
  72. PGContourList *gOutputContours;
  73.  
  74.  
  75. PGSense
  76. Compare( const ODPoint *p1, const ODPoint *p2 )
  77. {
  78.     if( p1->y > p2->y )
  79.         return kPositive;                        // p1 is below p2
  80.     else if( p1->y < p2->y )
  81.         return kNegative;                        // p1 is above p2
  82.     else if( p1->x > p2->x )
  83.         return kPositive;                        // p1 is directly right of p2
  84.     else if( p1->x < p2->x )
  85.         return kNegative;                        // p1 is directly left of p2
  86.     else
  87.         return kZero;                            // p1 is coincident with p2.
  88. }
  89.  
  90.  
  91. #if LOGGING
  92. void
  93. somPrintf( const ODPoint &pt )
  94. {
  95.     LOG("(%.2f,%.2f)", pt.x/65536.0,pt.y/65536.0);
  96. }
  97. #endif
  98.  
  99.  
  100. //=============================================================================
  101. // PGVertex
  102. //=============================================================================
  103.  
  104.  
  105. PGVertex::PGVertex( const ODPoint *pt, PGVertex *prev )
  106.     :ODPoint(*pt)
  107. {
  108.     if( prev ) {
  109.         fPrevious = prev;
  110.         fNext = prev->fNext;
  111.         fPrevious->fNext = this;
  112.         fNext->fPrevious = this;
  113.     } else
  114.         fPrevious = fNext = this;
  115. }
  116.  
  117.  
  118. void
  119. PGVertex::Reverse( )
  120. {
  121.     PGVertex *temp = fNext;
  122.     fNext = fPrevious;
  123.     fPrevious = temp;
  124. }
  125.  
  126.  
  127. void
  128. PGVertex::JamNext( PGVertex *next )
  129. {
  130.     fNext = next;
  131.     next->fPrevious = this;
  132. }
  133.  
  134.  
  135. //=============================================================================
  136. // PGContour
  137. //=============================================================================
  138.  
  139.  
  140. PGContour::PGContour( LinkedList *onList )
  141.     :Link(),
  142.      fFirst(kODNULL),
  143.      fLast(kODNULL),
  144.      fNVertices(0)
  145. {
  146.     if( onList )
  147.         onList->AddLast(this);
  148. }
  149.  
  150.  
  151. PGContour::~PGContour( )
  152. {
  153.     this->Remove();
  154.     
  155.     // Delete all vertices. Remember that PGContours are circular,
  156.     // while PGOutputContours are not.
  157.     PGVertex *v, *next;
  158.     for( v=fFirst; v; v=next ) {
  159.         next = v->GetNext();
  160.         if( next==fFirst )
  161.             next=kODNULL;
  162.         delete v;
  163.     }
  164. }
  165.  
  166.  
  167. PGContour*
  168. PGContour::InitContour( const ODContour *cont, Boolean reverse )
  169. {
  170.     fNVertices = cont->nVertices;
  171.     const ODPoint *prev = &cont->vertex[fNVertices-1];
  172.     const ODPoint *p = &cont->vertex[0];
  173.     if( reverse ) {
  174.         const ODPoint *temp = prev; prev=p; p=temp;
  175.     }
  176.  
  177.     BEGINLOG;
  178.     for( ODSLong n=fNVertices; n>0; n-- ) {
  179.         LOG(*p);
  180.         if( *p!=*prev ) {
  181.             PGVertex *v = new PGVertex(p,fLast);
  182.             if( !fFirst )
  183.                 fFirst = v;
  184.             fLast = v;
  185.             prev = p;
  186.         } else
  187.             fNVertices--;
  188.         if( reverse )
  189.             p--;
  190.         else
  191.             p++;
  192.     }
  193.     LOG("\n"); ENDLOG;
  194.     
  195.     if( fNVertices >= 3 )
  196.         return this;
  197.     else {
  198.         delete this;            // Not a proper contour, so bail out!
  199.         return kODNULL;
  200.     }
  201. }
  202.  
  203.  
  204. void
  205. PGContour::AddAllEvents( PGEventQueue &q )
  206. {
  207.     PGVertex *prev = fLast;
  208.     PGVertex *v = fFirst;
  209.     PGSense lastDir = Compare(prev,prev->GetPrevious());
  210.         
  211.     for( ODSLong i=fNVertices; i>0; i--, prev=v, v=v->GetNext() ) {
  212.         PGSense dir = Compare(v,prev);
  213.         if( lastDir<0 && dir>0 ) {                    // Ha! Local minimum
  214.             PGEvent *ev = (new PGEvent)->InitLocalMinEvent(prev);
  215.             q.Add(ev);
  216.         }
  217.         lastDir = dir;
  218.     }
  219. }
  220.  
  221.  
  222. //=============================================================================
  223. // PGOutputContour
  224. //=============================================================================
  225.  
  226.  
  227. PGOutputContour::PGOutputContour( const PGEdge* /*left*/, const PGEdge *right )
  228.     :PGContour(gOutputContours),
  229.      fWrapNo(right->fWrapNo),
  230.      fSense(right->fSense)
  231. {
  232.     // Clockwise contours have fSense>0, counterclockwise have fSense<0.
  233. }
  234.  
  235.  
  236. PGOutputContour::PGOutputContour( short x, short y )
  237.     :PGContour(kODNULL),
  238.      fWrapNo(1),
  239.       fSense(kPositive)
  240. {
  241.     // Used by Rgn2Poly() but not by the clipper.
  242.     
  243.     ODPoint pt(ff(x),ff(y));
  244.     this->AddVertex(kRight,&pt);
  245. }
  246.  
  247.  
  248. void
  249. PGOutputContour::AddVertex( PGSide side, const ODPoint *pt )
  250. {
  251.     // Negative-sense contours link their vertices from right to left!
  252.  
  253.     PGVertex *v = new PGVertex(pt,fLast);
  254.     if( side!=fSense || !fFirst )
  255.         fFirst = v;
  256.     if( side==fSense || !fLast )
  257.         fLast = v;
  258.     fNVertices++;
  259. }
  260.  
  261.  
  262. void
  263. PGOutputContour::AddVertex( PGSide side, short x, short y )
  264. {
  265.     // Used by Rgn2Poly() but not by the clipper.
  266.     
  267.     ODPoint pt( ff(x), ff(y) );
  268.     this->AddVertex(side,&pt);
  269. }
  270.  
  271.  
  272. void
  273. PGOutputContour::Close( )
  274. {
  275.     // Don't need to do anything (?)
  276. }
  277.  
  278.  
  279. void
  280. PGOutputContour::AppendContour( PGOutputContour *cont, PGSide toSide )
  281. {
  282.     fNVertices += cont->fNVertices;
  283.     
  284.     PGVertex *a, *b;
  285.     if( toSide==fSense ) {
  286.         a = fLast;
  287.         b = cont->fFirst;
  288.         fLast = cont->fLast;
  289.     } else {
  290.         a = cont->fLast;
  291.         b = fFirst;
  292.         fFirst = cont->fFirst;
  293.     }
  294.     a->JamNext(b);
  295.     
  296.     fLast->JamNext(fFirst);
  297.     
  298.     cont->fFirst = cont->fLast = kODNULL;
  299. }
  300.  
  301.  
  302. //=============================================================================
  303. // PGContourList
  304. //=============================================================================
  305.  
  306.  
  307. void
  308. PGContourList::ReadPolygon( const ODPolygon &poly, Boolean reverse, PGEventQueue &q )
  309. {
  310. #if RIGHT_HANDED_COORDS
  311.     reverse = !reverse;
  312. #endif
  313.  
  314.     ODSLong n = poly.GetNContours();
  315.     const ODContour *c;
  316.     for( c=poly.FirstContour(); n>0; n--,c=c->NextContour() ) {
  317.         LOG("    ");
  318.         PGContour *cont = (new PGContour(this))->InitContour(c,reverse);
  319.         if( cont )
  320.             cont->AddAllEvents(q);
  321.     }
  322. }
  323.  
  324.  
  325. void
  326. PGContourList::BuildPolygon( ODPolygon &poly )
  327. {
  328.     poly.Clear();
  329.     
  330.     ODSLong nContours = 0;
  331.     ODSLong *nVertices = new ODSLong[this->Count()];
  332.     
  333.     PGOutputContour *pgcont;
  334.     for( pgcont=(PGOutputContour*)this->First(); pgcont; pgcont=(PGOutputContour*)this->After(*pgcont) ) {
  335.         ODSLong n = pgcont->CountVertices();
  336.         if( n>=3 )
  337.             nVertices[nContours++] = n;
  338.     }
  339.     
  340.     LOG("$ Building output polygon with %d contours...\n", nContours);
  341.     
  342.     if( nContours==0 ) {
  343.         delete nVertices;
  344.         return;
  345.     }
  346.     
  347.     TRY{
  348.         poly.SetContours(nContours,nVertices);
  349.     }CATCH_ALL{
  350.         delete nVertices;
  351.         RERAISE;
  352.     }ENDTRY
  353.     delete nVertices;
  354.     
  355.     BEGINLOG;
  356.     ODContour *cont = poly.FirstContour();
  357.     pgcont = (PGOutputContour*)this->First();
  358.     for( ODSLong i=nContours; i>0; i-- ) {
  359.         while( pgcont->CountVertices()<3 )
  360.             pgcont = (PGOutputContour*)pgcont->GetNext();            // Skip unwanted contours
  361.         
  362. #if RIGHT_HANDED_COORDS
  363.             PGVertex *vert = pgcont->Last();
  364. #else
  365.             PGVertex *vert = pgcont->First();
  366. #endif
  367.         for( ODSLong j=0; j<cont->nVertices; j++ ) {
  368.             LOG(*vert); LOG(" ");
  369.             cont->vertex[j] =*vert;
  370. #if RIGHT_HANDED_COORDS
  371.             vert = vert->GetPrevious();
  372. #else
  373.             vert = vert->GetNext();
  374. #endif
  375.         }
  376.         LOG("\n");
  377.         pgcont = (PGOutputContour*)pgcont->GetNext();
  378.         cont = cont->NextContour();
  379.     }
  380.     ENDLOG;
  381. }
  382.